0-1 Knapsack Problem

Problem

Solution

Problem​

Solution​

Problem Description

Testcases

Subproblems

Recurrence Relation

Base Cases

Edge Cases

Solving the Problem

Space Optimization

Implementation

Problem Description​

Testcases​

Subproblems​

Recurrence Relation​

Base Cases​

Edge Cases​

Solving the Problem​

Space Optimization​

Implementation​

This is a type of problem where the goal is to maximize the profit given a fixed-size capacity and a set of items with their weights and values.

You are given a knapsack with a maximum weight capacity of $W$ and $n$ items $V = \{(w_1, v_1), (w_2, v_2), ..., (w_n, v_n)\}$ where $w_i$ is the weight of the $i$ -th item and $v_i$ is the value of the $i$ -th item.

You have to maximize the value of the knapsack by choosing some of the items such that the total weight of the chosen items is less than or equal to $W$ .

You either not choose an item, or choose it once.

Given:

0 <= W
0 <= n
0 <= w[i]

Input: W = 5, V = { (2, 20), (1, 10), (4, 30), (3, 15) }
Output: 40

The optimal choices are { 2, 3 }.
The total weight is 1 + 4 = 5.
The total value is 10 + 30 = 40.

Input: W = 10, V = { (2, 10), (3, 15), (5, 20), (7, 30), (4, 12) }
Output: 45

The optimal choices are { 1, 2, 3 } or { 1, 2, 4 }.
The total weight is 3 + 7 = 10 or 2 + 3 + 5 = 10.
The total value is 15 + 30 = 45 or 10 + 15 + 20 = 45.

This problem shows that the parameters may not only change by a constant amount.

And here the parameters does not only mean the parameter of the overall problem, but also the parameters of the subproblems.

The most important part of this solution, is to recognize that the parameters are interdependent.

We can see that at a given point, for example, with $W$ capacity remaining, we have already decided on the items to take from the first $i$ items.

From here, the optimal solution can be from the following previous subproblems:

With $W - w_i$ capacity remaining, we took the $i$ -th item.
With $W - w_{i-1}$ capacity remaining, we took the $i - 1$ -th item.
... and so on.
With $W - w_2$ capacity remaining, we took the $2$ -nd item.
With $W - w_1$ capacity remaining, we took the $1$ -st item.
With $W$ capacity remaining, we didn't take any item at all.

We can see the subproblems may change depending on the weight $w_i$ of each item $i$ .

We can apply a dynamic programming technique to the subproblems, and know that the following part:

With $W - w_{i-1}$ capacity remaining, we took the $i - 1$ -th item.
With $W - w_{i-2}$ capacity remaining, we took the $i - 2$ -th item.
... and so on.
With $W - w_2$ capacity remaining, we took the $2$ -nd item.
With $W - w_1$ capacity remaining, we took the $1$ -st item.
With $W$ capacity remaining, we didn't take any item at all.

is the subproblems when we have $W$ capacity remaining and already decided on the items to take from the first $i - 1$ items, meaning we didn't take the $i$ -th item.

So the optimized subproblems are:

With $W - w_i$ capacity remaining, we took the $i$ -th item.
With $W$ capacity remaining, we didn't take the $i$ -th item.

The relation is simple, since we need the maximum value, we can take the one with the maximum value among all the subproblems.

Let $f(i, W)$ be the maximum value we can get from the first $i$ items with a capacity of $W$ :

f(i, W) = \max \begin{cases} f(i - 1, W - w_i) + v_i \\ f(i - 1, W) \end{cases}

The base cases for this problem is when we have no items left, or when we have no capacity left.

In both cases, we be able to take any item and allocate to the capacity, so the value is 0.

\begin{aligned} f(0, W) &= 0 \\ f(i, 0) &= 0 \end{aligned}

Since we don't want the capacity to be negative, we need to exclude cases if the capacity will become negative (or return 0 since it is the smallest possible value).

f(i, W) = \max \begin{cases} f(i - 1, W - w_i) + v_i & \text{if } W - w_i \ge 0 \\ ... \end{cases}

We can initialize the memoization array with 0, and skip the base cases in the loop.

0-1 Knapsack Problem
function zero_one_knapsack(W: int, V: (w: int, v: float)[]) {
    // problem size
    let n = V.length

    // initialize memoization array
    let dp = [...] of size (n + 1, W + 1)
             zero-based index
             initialized to 0
    
    // calcualate values
    for i from 1 to n {
        for w from 1 to W {
            if w - V[i].w >= 0 {
                dp[i][w] = max(
                    dp[i - 1][w - V[i].w] + V[i].v,
                    dp[i - 1][w],
                )
            } else {
                dp[i][w] = dp[i - 1][w]
            }
        }
    }

    return dp[n][W]
}

Time Complexity: $O(nW)$

Space Complexity: $O(nW)$

The solution to the knapsack problem with $W = 5$ and $V = \{(2, 20), (1, 10), (4, 30), (3, 15)\}$ .

Try it out

$W =\:$

, $V(w, v) = \{$

$\}$

Green bold values form a combination of items to maximize the value of the knapsack, and underlined values are where the items were taken.

Since we only need the previous item's values to calculate the next item's values, we can use a 1D array to store the values.

However, since we may need the previous item's value at an unknown index, we can use a copy of the previous array for calculation to avoid getting overriden.

Here we will use a 2D array with 2 rows for better visualization.

0-1 Knapsack Problem - Space Optimized
function zero_one_knapsack(W: int, V: (w: int, v: float)[]) {
    // problem size
    let n = V.length

    // initialize memoization array
    let dp = [...] of size (2, W + 1)
             zero-based index
             initialized to 0
    
    // calcualate values
    for i from 1 to n {
        // copy the previous row
        dp[0] = dp[1].copy()

        for w from 1 to W {
            if w - V[i].w >= 0 {
                dp[1][w] = max(
                    dp[0][w - V[i].w] + V[i].v,
                    dp[0][w],
                )
            } else {
                dp[1][w] = dp[0][w]
            }
        }
    }

    return dp[W]
}

Time Complexity: $O(nW)$

Space Complexity: $O(W)$

The space optimized solution to the knapsack problem with $W = 5$ and $V = \{(2, 20), (1, 10), (4, 30), (3, 15)\}$ .

Possibility of Optimizing to O(n) Space Complexity

We need to know which previous index value to take from the memoization array, and the relation between current and previous index value must be a constant for it to be optimizable.

However, $w$ does not meet these requirements, so it is not possible to optimize out the $W$ in the space complexity.

We can use it on $i$ because we know it only need the $i-1$ value, thus we are able to optimize out the $n$ in the space complexity.

Checkpoint

What is the difference of the knapsack problem compared to other dynamic programming problems like edit distance and unique paths?

There is no difference

Position of some subproblems depend on the value of the items

Position of some subproblems depend on the weight of the items

Items can be from any index on the previous row of the memoization array

Python
C++
Rust

To follow the Python naming convention, we will name $W$ as capacity and $V$ as items.

items will be a list of Item objects:

Item Class
class Item:
    weight: int
    value: float

    def __init__(self, weight: int, value: float):
        self.weight = weight
        self.value = value

0-1 Knapsack Problem
def zeroOneKnapsack(capacity: int, items: list[Item]):
    # the problem size
    n = len(items)

    # initialize memoization array
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    # calculate values
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if w - items[i - 1].weight >= 0:
                dp[i][w] = max(
                    dp[i - 1][w - items[i - 1].weight] + items[i - 1].value,
                    dp[i - 1][w],
                )
            else:
                dp[i][w] = dp[i - 1][w]

    return dp[n][capacity]

0-1 Knapsack Problem - Space Optimized
def zeroOneKnapsack(capacity: int, items: list[Item]):
    # the problem size
    n = len(items)

    # initialize memoization array
    dp = [[0] * (capacity + 1) for _ in range(2)]

    # calculate values
    for i in range(1, n + 1):
        # copy the previous row
        dp[0] = dp[1][:]

        for w in range(1, capacity + 1):
            if w - items[i - 1].weight >= 0:
                dp[1][w] = max(
                    dp[0][w - items[i - 1].weight] + items[i - 1].value,
                    dp[0][w],
                )
            else:
                dp[1][w] = dp[0][w]

    return dp[1][capacity]

To follow the C++ naming convention, we will name $W$ as capacity and $V$ as items.

items will be a vector of Item structs:

Item Struct
struct Item {
    int weight;
    float value;
};

0-1 Knapsack Problem
#include <vector>
#include <algorithm>

float zero_one_knapsack(int capacity, std::vector<Item> items) {
    // the problem size
    int n = items.size();

    // initialize memoization array
    std::vector<std::vector<float>> dp(
        n + 1,
        std::vector<float>(capacity + 1, 0)
    );

    // calculate values
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= capacity; w++) {
            if (w - items[i - 1].weight >= 0) {
                dp[i][w] = std::max(
                    dp[i - 1][w - items[i - 1].weight] + items[i - 1].value,
                    dp[i - 1][w]
                );
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][capacity];
}

0-1 Knapsack Problem - Space Optimized
#include <vector>
#include <algorithm>

float zero_one_knapsack(int capacity, std::vector<Item> items) {
    // the problem size
    int n = items.size();

    // initialize memoization array
    std::vector<std::vector<float>> dp(
        2,
        std::vector<float>(capacity + 1, 0)
    );

    // calculate values
    for (int i = 1; i <= n; i++) {
        // copy the previous row
        dp[0] = dp[1];

        for (int w = 1; w <= capacity; w++) {
            if (w - items[i - 1].weight >= 0) {
                dp[1][w] = std::max(
                    dp[0][w - items[i - 1].weight] + items[i - 1].value,
                    dp[0][w]
                );
            } else {
                dp[1][w] = dp[0][w];
            }
        }
    }

    return dp[1][capacity];
}

To follow the Rust naming convention, we will name $W$ as capacity and $V$ as items.

items will be a Vec of Item structs:

Item Struct
struct Item {
    weight: usize,
    value: f32,
}

0-1 Knapsack Problem
fn zero_one_knapsack(capacity: usize, items: Vec<Item>) -> f32 {
    // the problem size
    let n = items.len();

    // initialize memoization array
    let mut dp = vec![vec![0.0; capacity + 1]; n + 1];

    // calculate values
    for i in 1..=n {
        for w in 1..=capacity {
            if w >= items[i - 1].weight {
                dp[i][w] = f32::max(
                    dp[i - 1][w - items[i - 1].weight] + items[i - 1].value,
                    dp[i - 1][w],
                );
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    dp[n][capacity]
}

0-1 Knapsack Problem - Space Optimized
fn zero_one_knapsack(capacity: usize, items: Vec<Item>) -> f32 {
    // the problem size
    let n = items.len();

    // initialize memoization array
    let mut dp = vec![vec![0.0; capacity + 1]; 2];

    // calculate values
    for i in 1..=n {
        // copy the previous row
        dp[0] = dp[1].clone();

        for w in 1..=capacity {
            if w >= items[i - 1].weight {
                dp[1][w] = f32::max(
                    dp[0][w - items[i - 1].weight] + items[i - 1].value,
                    dp[0][w],
                );
            } else {
                dp[1][w] = dp[0][w];
            }
        }
    }

    dp[1][capacity]
}

(1, 10)

(4, 30)